package com.lxl.bucket;


import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * @Classname BucketSort
 * @Description 桶排序
 * 稳定排序
 * 时间复杂度：O(N + C); C = N * (logN - logM)
 * N：待排数据
 * M：桶数量
 */
public class BucketSort {
    // 桶的数量
    private static final int BUCKET_NUM = 10;

    public static void main(String[] args) {
        // 测试数据
        int arr[] = {37,18,21,21,49,0,25,6,14};
        // 测试输出
        bucketSort(arr,arr.length);

    }

    /**
     * 桶排序
     * @param arr
     * @param len
     */
    public static void bucketSort(int[] arr,int len){

        // 求取最大值最小值，确定桶区间范围
        // 记录数组中的最大值
        int max = Integer.MIN_VALUE;
        // 记录数组中的最小值
        int min = Integer.MAX_VALUE;
        for (int i = 0;i<len;i++){
            max = Math.max(max,arr[i]);
            min = Math.min(min,arr[i]);
        }
        System.out.println("最大值："+max);
        System.out.println("最小值："+min);

        // 桶数
        int bucketNum = (max - min) / arr.length + 1;
        System.out.println("桶数 " + bucketNum);
        ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum);
        for (int i = 0;i<bucketNum;i++){
            bucketArr.add(new ArrayList<Integer>());
        }

        // 把每个元素放入桶
        for (int i = 0;i<len;i++){
            int num = (arr[i] - min) / len;
            System.out.println("num:"+arr[i]+"     index of num :" + num);
            bucketArr.get(num).add(arr[i]);
        }

        // 对每个桶进行排序
        for (int i = 0;i<bucketArr.size();i++){
            Collections.sort(bucketArr.get(i));
        }
        // 输出排序后的桶数据
        System.out.println(bucketArr.toString());

        //合成新数组
        int i = 0;
        for (ArrayList<Integer> arrItem:bucketArr){
            if (arrItem.size()!=0){
                for (int item:arrItem){
                    arr[i++]=item;
                }
            }
        }
        System.out.println(Arrays.toString(arr));
    }
}
